class Solution {
    //目标和
    public int ret;
    public int path;
    public int a;
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for(int i = 0; i < nums.length; i++){
            sum += nums[i];
        }
        a = (target + sum) / 2;
        if((target + sum) % 2 == 1) return 0;
        ret = 0;
        path = 0;
        dfs(nums, 0);
        return ret;
    }
    public void dfs(int[] nums, int index){
        //递归出口
        if(path == a){
            ret++;
            // return;
        }
        //函数体
        for(int i = index; i < nums.length; i++){
            path += nums[i];
            dfs(nums, i + 1);//递归
            path -= nums[i];//回溯
        }
    }
}